#include <iostream>
#include <stack>

struct Node
{
    int _value;
    Node *_p_next;

    Node(int value) : _value(value), _p_next(nullptr) {}
};

// 尾插
void PushBack(Node **phead, int value)
{
    if (phead == nullptr)
        return;
    // 头指针为空
    if (*phead == nullptr)
    {
        *phead = new Node(value);
    }
    else
    {
        Node *prev = *phead;
        while (prev->_p_next != nullptr)
        {
            prev = prev->_p_next;
        }
        prev->_p_next = new Node(value);
    }
}

// 删除一个节点
void Erase(Node **phead, int value) // 传二级指针是为了改变头部的时候的正确性
{
    if (phead == nullptr || *phead == nullptr)
        return;

    Node *delete_node = nullptr;
    // 头删
    if ((*phead)->_value == value)
    {
        delete_node = *phead;
        *phead = (*phead)->_p_next;
    }
    else
    {
        // 找到待删除的节点
        Node *prev = *phead;
        while (prev->_p_next != nullptr && prev->_p_next->_value != value)
        {
            prev = prev->_p_next;
        }
        if (prev->_p_next != nullptr)
        {
            delete_node = prev->_p_next;
            prev->_p_next = delete_node->_p_next;
        }
    }
    if (delete_node != nullptr)
    {
        delete delete_node;
        delete_node = nullptr;
    }
}

// 生成一个链表
Node *CreateList()
{
    Node *phead = new Node(1);
    PushBack(&phead, 2);
    PushBack(&phead, 3);
    PushBack(&phead, 4);
    PushBack(&phead, 5);
    PushBack(&phead, 6);

    return phead;
}

// 使用栈的思想
void Stack_PrintList(Node *phead)
{
    if (phead == nullptr)
        return;
    std::stack<Node *> st;
    Node *cur = phead;

    // 遍历
    while (cur)
    {
        st.push(cur);
        cur = cur->_p_next;
    }

    // 打印
    while (!st.empty())
    {
        Node *node = st.top();
        std::cout << node->_value << "--";
        st.pop();
    }
    std::cout << "nullptr" << std::endl;
}

// 递归的思想
void R_PrintList(Node *phead)
{
    if (phead == nullptr)
        return;
    R_PrintList(phead->_p_next);
    std::cout << phead->_value << std::endl;
}

int main()
{
    // 创建一个链表
    Node *phead = CreateList();
    // 倒着打印
    // Stack_PrintList(phead);
    // Stack_PrintList(nullptr);
    // R_PrintList(phead);
    // R_PrintList(nullptr);

    Node *tmp = new Node(1);
    Stack_PrintList(tmp);
    R_PrintList(tmp);
    return 0;
}